package algorithm.sort;

import java.util.Arrays;

/**
 * 选择排序
 * 算法的概念
 *      原地排序：原地排序算法，就是特指空间复杂度是 O(1) 的排序算法。
 *      稳定性：这个概念是说，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。
 *
 *
 * @author DengZhiYuan
 * @version 1.0
 * @date 2022/3/29 18:51
 */
public class ChooseSort {

    public static void main(String[] args) {

//        new ChooseSort().bubbleSortV1(new int[]{22,100,87,4,4,3,1,5,6,7,11});
        ChooseSort chooseSort = new ChooseSort();
        int[] ints = {22, 100, 87, 4, 4, 3, 1, 5, 6, 7, 11,6, 7, 11};
        chooseSort.insertSortV2(ints,ints.length);

//        Arrays.sort(ints);
    }
    /**
     * 冒泡排序-版本1
     * @author DengZhiYuan
     * @version 1.0
     * @date 2022/4/4 11:25
     * @param arr
     * @return
     */
    public void bubbleSortV1(int[] arr){
        int len = arr.length;
        for (int i = 0; i < len-1; i++) {
            for (int j = 0; j+i+1 < len; j++) {
                if(arr[j] > arr[j+1]){
                    int temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 冒泡排序-版本2
     * @author DengZhiYuan
     * @version 1.0
     * @date 2022/4/4 11:25
     * @param arr
     * @return
     */
    public void bubbleSortV2(int[] arr){
        int len = arr.length;
        if(len <= 1){
            return;
        }
        for (int i = 0; i < len; i++) {
            //提前退出 优化
            boolean flag = false;
            for (int j = 0; j < len-i-1; j++) {
                if(arr[j] > arr[j+1]){
                    int temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                    flag = true;
                }
            }
            if(!flag){
                break;
            }
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 插入排序-版本1  从前向后排序
     * @author DengZhiYuan
     * @version 1.0
     * @date 2022/4/4 11:25
     * @param arr
     * @return
     */
    public void insertSortV1(int[] arr,int n){
        if(n <= 1) return;
        for (int i = 1; i < arr.length; i++) {
            int value = arr[i];
            for (int j = i-1; j >= 0; j--) {
                if(value < arr[j]){
                    arr[j+1] = arr[j];
                }else{
                    arr[j+1] = value;
                    break;
                }
                if(j == 0){
                    arr[0] = value;
                    break;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
    /**
     * 插入排序-版本2 - 从小到大 - jdk版本
     * @author DengZhiYuan
     * @version 1.0
     * @date 2022/4/4 11:25
     * @param arr
     * @return
     */
    public void insertSortV2(int[] arr,int n){
        if(n <= 1) return;
        for (int i = 0,j=i; i < arr.length-1; j = ++i) {
            int ai = arr[i+1];
            while (ai < arr[j]){
                arr[j+1] = arr[j];
                if( --j < 0){
                    break;
                }
            }
            arr[j+1] = ai;
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 选择排序-版本1  从前向后排序
     * @author DengZhiYuan
     * @version 1.0
     * @date 2022/4/4 11:25
     * @param arr
     * @return
     */
    public void selectSortV1(int[] arr,int n){
        if(n <= 1) return;
        for (int i = 0; i < arr.length-1; i++) {
            int minIdx = i;
            int value = arr[i];
            for (int j = i+1; j < arr.length; j++) {
                if(value > arr[j]){
                    minIdx = j;
                    value = arr[j];
                }
            }
            if(i != minIdx){
                arr[minIdx] = arr[i];
                arr[i] = value;
            }
        }
        System.out.println(Arrays.toString(arr));
    }



}
